#!/usr/bin/python

from cell import Cell
from util import Util
class Node:
    @staticmethod
    def createLeaf(degree = None):
        return Node(True, degree)
    @staticmethod
    def createInterior(degree = None):
        return Node(False, degree)

    def __init__(self, isLeaf = True, degree = None):
        self.__cells =  []
        self.__biggestNode = None;
        self.__isLeaf = isLeaf
        self.__degree = degree is not None and degree or 2
        self.__maxCellsNo = 2 * self.__degree - 1

    def createEmpty(self):
        return Node(self.__isLeaf, self.__degree)
    
    def __str__(self):
        def strNode(node):
            return "IsLeaf:%s, Used:%d of %d" % (node.isLeaf(), node.used(), node.getMaxCellsNo())
        def strCells(cells):
            return "cells:[" + ", ".join([str(c) for c in cells]) + "]"
        def strBiggestNode(biggestNode):
            return "(biggest:%x)" % Util.getId(biggestNode)

        return "{%s | %s | %s}" % (strNode(self) , strCells(self.__cells) , strBiggestNode(self.__biggestNode))

    # insert to leaf node with ordered TODO: no data
    def insertToLeaf(self, key):
        assert self.__isLeaf
        self.append(key)
        for i in range(self.used()-1, 0, -1):
            if self.__cells[i].getKey() < self.__cells[i-1].getKey():
                tmp = self.__cells[i]
                self.__cells[i] = self.__cells[i-1]
                self.__cells[i-1] = tmp
        #end for
    #end def

    # insert to index cells
    def insert(self, index, key, node = None, data=None):
        if index >= 0 and index < self.used():
            self.__cells.insert(index, Cell(key, node, data))
            return True
        print "Error: out of range"
        return False
    ##end insert

    def append(self, key, node = None):
        return self.appendCell(Cell(key, node))
    #end def
    def appendCell(self, cell):
        if len(self.__cells) < self.getMaxCellsNo():
            self.__cells.append(cell)
            if cell.getNode() is not None:
                self.__isLeaf = False
            return True
        return False
    #end def

    def setBiggestNode(self, node):
        self.__biggestNode = node
    def getBiggestNode(self):
        return self.__biggestNode

    def toInterior(self):
        self.__isLeaf = False
    def toLeaf(self):
        self.__isLeaf = True
    def isLeaf(self):
        return self.__isLeaf

    def used(self):
        return len(self.__cells)
    def getMaxCellsNo(self):
        return self.__maxCellsNo
    def getDegree(self):
        return self.__degree

    def getCells(self):
        return self.__cells
    def getCell(self, index):
        return self.__cells[index]
    def deleteCell(self, index):
        del self.__cells[index]
    def deleteAfter(self, index):
        del(self.__cells[index:])

import unittest
class TestNode(unittest.TestCase):
    def testCreateRoot(self):
        n = Node.createLeaf()
        self.assertTrue(n.isLeaf())
        self.assertEqual(3, n.getMaxCellsNo())
        n.append("M")
        print "\n", n

    def __createNode(self):
        bc_node = Node.createLeaf()
        bc_node.append("B")
        bc_node.append("C")
        self.assertTrue(bc_node.isLeaf())
        self.assertEqual(bc_node.used(), 2)

        fg_node = Node.createLeaf()
        fg_node.append("F")
        fg_node.append("G")

        jkl_node = Node.createLeaf()
        jkl_node.append("J")
        jkl_node.append("K")
        jkl_node.append("L")

        dh_node = Node.createInterior()
        dh_node.append("D", bc_node)
        dh_node.append("H", fg_node)
        dh_node.setBiggestNode(jkl_node)
        self.assertFalse(dh_node.isLeaf())
        self.assertEqual(dh_node.used(), 2)
        #print( "dh_node : %s"  % dh_node)


        np_node = Node.createLeaf()
        np_node.append("N")
        np_node.append("P")

        rs_node = Node.createLeaf()
        rs_node.append("R")
        rs_node.append("S")

        vw_node = Node.createLeaf()
        vw_node.append("V")
        vw_node.append("W")

        yz_node = Node.createLeaf()
        yz_node.append("Y")
        yz_node.append("Z")

        qtx_node = Node.createInterior()
        qtx_node.append("Q", np_node)
        qtx_node.append("T", rs_node)
        qtx_node.append("X", vw_node)
        qtx_node.setBiggestNode(yz_node)
        #print(qtx_node)

        root = Node.createInterior()
        root.append("M", dh_node)
        root.setBiggestNode(qtx_node)
        #print(root)
        return root
        
    def testNode(self):
        print self.__createNode()


if __name__ == "__main__":
    suite = unittest.TestSuite([
        unittest.TestLoader().loadTestsFromTestCase(TestNode),
    ])
    unittest.TextTestRunner(verbosity=2).run(suite)
